#include <stdio.h>
#include <stdlib.h>
#define TRUE 1
#define FALSE 0
#define OK  1
#define ERROR  0
#define INFEASIBLE -1
#define OVERFLOW -2
#define STACK_INIT_SIZE 1000
#define STACKINCREMENT 100
#define MAXQSIZE 1000
typedef int  Status;
typedef int  ElemType;
typedef struct BiTNode {
    ElemType data;
    struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;
typedef BiTree QElemType;   //队列
typedef BiTree SElemType;   //栈
typedef struct {
    SElemType *base;
    SElemType *top;
    int stackszie;
} SqStack;
//初始化栈
Status InitStack(SqStack &S) {
    //申请空间
    S.base = (SElemType *)malloc(sizeof(SElemType) * STACK_INIT_SIZE);
    if(!S.base) return ERROR;
    S.top = S.base;
    S.stackszie = STACK_INIT_SIZE;
    return OK;
}
//清空栈
Status StackEmpty(SqStack S) {
    if(S.top == S.base)
        return OK;
    else
        return ERROR;
}
//获取栈顶元素
Status GetTop(SqStack S, SElemType &e) {
    if(S.top == S.base) return ERROR;
    e = *(S.top - 1);
    return OK;
}
//入栈
Status Push(SqStack &S, SElemType e) {
    if(S.top - S.base >= S.stackszie) {
        S.base = (SElemType*)realloc(S.base, sizeof(SElemType) * (S.stackszie + STACKINCREMENT));
        if(!S.base) return ERROR;
        S.stackszie += STACKINCREMENT;
        S.top = S.base + S.stackszie;
    }
    *(S.top++) = e;
    return OK;
}
//出栈
Status Pop(SqStack &S, SElemType &e) {
    if(S.top == S.base) return ERROR;
    e = *(--S.top);
    return OK;
}
typedef struct {
    QElemType *base;
    int front;
    int rear;
} SqQueue;
//初始化队列
Status InitQueue(SqQueue &Q) {
    Q.base = (QElemType*)malloc(sizeof(QElemType) * MAXQSIZE);
    if(!Q.base) return ERROR;
    Q.front = Q.rear = 0;
    return OK;
}
//入队
Status EnQueue(SqQueue &Q, QElemType e) {
    //队列满
    if((Q.rear + 1) % MAXQSIZE == Q.front) return ERROR;
    Q.base[Q.rear] = e;
    Q.rear = (Q.rear + 1) % MAXQSIZE;
    return OK;
}
//出队
Status DeQueue(SqQueue &Q, QElemType &e) {
    if(Q.front == Q.rear) return ERROR;
    e = Q.base[Q.front];
    Q.front = (Q.front + 1) % MAXQSIZE;
    return OK;
}
Status Insert(BiTree &T) {
    BiTree A, B;
    ElemType e;
    scanf("%d", &e);
    //初始化根结点
    if(!T) {
        if(!(T = (BiTree)malloc(sizeof(BiTNode)))) return ERROR;
        T->data = e;
        T->lchild = NULL;
        T->rchild = NULL;
        return OK;
    }//end if
    else {
        if(!(A = (BiTree)malloc(sizeof(BiTNode)))) return ERROR;
        A->data = e;
        A->lchild = NULL;
        A->rchild = NULL;
        B = T;
        //建立有序树
        while(1) {
            if(B->data <= A->data) {
                if(!B->rchild) {
                    B->rchild = A;
                    return OK;
                }
                else {
                    B = B->rchild;
                }
            }
            else {
                if(!B->lchild) {
                    B->lchild = A;
                    return OK;
                }
                else {
                    B = B->lchild;
                }
            }
        }
        T = B;
        return OK;
    }
}
Status PrintElement(ElemType e) {
    printf("%d ", e);
    return OK;
}
//先序遍历递归算法
Status PreOrderTraverse(BiTree T, Status(*Visit)(ElemType)) {
    if(T) {
        Visit(T->data);
        PreOrderTraverse(T->lchild, Visit);
        PreOrderTraverse(T->rchild, Visit);
    }
    return OK;
}
//中序遍历递归算法
Status InOrderTraverse(BiTree T, Status(*Visit)(ElemType)) {
    if(T) {
        InOrderTraverse(T->lchild, Visit);
        Visit(T->data);
        InOrderTraverse(T->rchild, Visit);
    }
    return OK;
}
//后序遍历递归算法
Status PostOrderTraverse(BiTree T, Status(*Visit)(ElemType)) {
    if(T) {
        PostOrderTraverse(T->lchild, Visit);
        PostOrderTraverse(T->rchild, Visit);
        Visit(T->data);
    }
    return OK;
}
//非递归中序遍历
Status MidTraverse(BiTree T) {
    BiTree S1;
    SqStack S2;
    S1 = T;
    InitStack(S2);
    while(S1 || S2.base != S2.top) {
        if(S1) {
            Push(S2, S1);
            S1 = S1->lchild;
        }//左子树
        else {
            Pop(S2, S1);
            printf("%d ", S1->data);
            S1 = S1->rchild;
        }//右子树
    }
    return OK;
}

Status FTraverse(BiTree T) {
    BiTree A, L, R;
    SqQueue Q;
    InitQueue(Q);
    A = T;
    EnQueue(Q, T);
    while(Q.front != Q.rear) {
        DeQueue(Q, A);
        printf("%d ", A->data);
        L = A->lchild;
        R = A->rchild;
        if(L) EnQueue(Q, L);
        if(R) EnQueue(Q, R);
    }
    return OK;
}

Status search(BiTree T, ElemType e) {
    BiTree A;
    A = T;
    while(A) {
        if(A->data < e)
            A = A->rchild;
        else if(A->data > e)
            A = A->lchild;
        else return OK;
    }
    return ERROR;
}
int main() {
    BiTree T = NULL;
    int n, i, e;
    scanf("%d", &n);
    for(i = 0; i < n; i++)
        Insert(T);
    PreOrderTraverse(T, PrintElement);
    printf("\n");
    InOrderTraverse(T, PrintElement);
    printf("\n");
    PostOrderTraverse(T, PrintElement);
    printf("\n");
    scanf("%d", &e);
    printf("%d\n", search(T, e));
    scanf("%d", &e);
    printf("%d\n", search(T, e));
    Insert(T);
    PreOrderTraverse(T, PrintElement);
    printf("\n");
    InOrderTraverse(T, PrintElement);
    printf("\n");
    PostOrderTraverse(T, PrintElement);
    printf("\n");
    MidTraverse(T);
    printf("\n");
    FTraverse(T);
}
//Description 用函数实现如下二叉排序树算法：
//（1）   插入新结点
//（2）   前序、中序、后序遍历二叉树
//（3）   中序遍历的非递归算法
//（4）   层次遍历二叉树
//（5）   在二叉树中查找给定关键字(函数返回值为成功1,失败0)
//
//
//输入格式
//第一行：准备建树的结点个数n
//第二行：输入n个整数，用空格分隔
//第三行：输入待查找的关键字
//第四行：输入待查找的关键字
//第五行：输入待插入的关键字
//
//
//输出格式
//第一行：二叉树的先序遍历序列
//第二行：二叉树的中序遍历序列
//第三行：二叉树的后序遍历序列
//第四行：查找结果
//第五行：查找结果
//第六行~第八行：插入新结点后的二叉树的先、中、序遍历序列
//第九行：插入新结点后的二叉树的中序遍历序列(非递归算法)
//第十行：插入新结点后的二叉树的层次遍历序列
//
//
//输入样例
//7
//40 20 60 18 50 56 90
//18
//35
//30
//
//
//输出样例
//40 20 18 60 50 56 90
//18 20 40 50 56 60 90
//18 20 56 50 90 60 40
//1
//0
//40 20 18 30 60 50 56 90
//18 20 30 40 50 56 60 90
//18 30 20 56 50 90 60 40
//18 20 30 40 50 56 60 90
//40 20 60 18 30 50 90 56
